package com.nowcoder.code.hjnc;

import com.algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

public class NC8 {

    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    LinkedList<Integer> tmp = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        path(root, sum);
        return list;
    }

    int now = 0;

    public void path(TreeNode node, int sum) {
        if (node == null) return;

        tmp.add(node.val);
        now = now + node.val;

        if (node.right == null && node.left == null && now == sum) {
            list.add(new ArrayList<>(tmp));
            tmp.removeLast();
            now = now - node.val;
            return;
        }

        path(node.left, sum);
        path(node.right, sum);
        tmp.removeLast();
        now = now - node.val;
    }

}
